home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / MAIN.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-14  |  12.1 KB  |  326 lines
  1. /*
  2.     Module: main.c
  3.     Purpose: Main driver for minimization routines
  4.  
  5.     This is a complex main program supporting what is actually about 30
  6.     different programs.  The options available are listed in "usage" which
  7.     is usually kept up-to-date.
  8. */
  9.  
  10. #define EXTERN
  11. #define INIT
  12. #include "espresso.h"
  13.  
  14. void runtime()
  15. {
  16.     int i;
  17.     double total = 0.001;
  18.  
  19.     for(i = 0; i < TIME_COUNT; i++)
  20.         total += total_time[i];
  21.     for(i = 0; i < TIME_COUNT; i++)
  22.         if (total_calls[i] != 0)
  23.             printf("# %s\t%2d call(s) for %s (%3.1f%%)\n",
  24.             total_name[i], total_calls[i], print_time(total_time[i]),
  25.             total_time[i]/total*100.0);
  26. }
  27.  
  28.  
  29. init_runtime()
  30. {
  31.     total_name[READ_TIME] =     "READ       ";
  32.     total_name[COMPL_TIME] =    "COMPL      ";
  33.     total_name[REDUCE_TIME] =   "REDUCE     ";
  34.     total_name[EXPAND_TIME] =   "EXPAND     ";
  35.     total_name[ESSEN_TIME] =    "ESSEN      ";
  36.     total_name[IRRED_TIME] =    "IRRED      ";
  37.     total_name[GREDUCE_TIME] =  "REDUCE_GASP";
  38.     total_name[GEXPAND_TIME] =  "EXPAND_GASP";
  39.     total_name[GIRRED_TIME] =   "IRRED_GASP ";
  40.     total_name[MV_REDUCE_TIME] ="MV_REDUCE  ";
  41.     total_name[RAISE_IN_TIME] = "RAISE_IN   ";
  42.     total_name[VERIFY_TIME] =   "VERIFY     ";
  43. }
  44.  
  45. #define option(a) (equal(what_to_do, a))
  46.  
  47. usage()
  48. {
  49.     printf("%s\n\n", VERSION);
  50.     printf("SYNOPSIS:\n\tespresso [type] [file] [options]\n\n");
  51.     printf("[type] provides the logical form of the input file\n");
  52.     printf("\t-f\tFile specifies ON-set\n");
  53.     printf("\t-fd\tFile specifies ON-set and DC-set (default)\n");
  54.     printf("\t-fr\tFile specifies ON-set and OFF-set\n");
  55.     printf("\t-fdr\tFile specifies ON-set, OFF-set, and DC-set\n\n");
  56.     printf("[options] allowed are:\n");
  57.     printf("\t-d\tProvide verbose detail of program execution\n");
  58.     printf("\t-fast\tStop after first EXPAND/IRRED\n");
  59.     printf("\t-ness\tDo not remove essential primes\n");
  60.     printf("\t-nirr\tDo not force the result to be irredundant\n");
  61.     printf("\t-out xx\tSpecify output format as F, FD, FR, or FDR\n");
  62.     printf("\t-pos\tSwap ON-set and OFF-set\n");
  63.     printf("\t-s\tProvide short execution summary\n");
  64.     printf("\t-t\tProvide longer execution trace\n");
  65.     printf("\t-x\tSuppress printing of solution\n");
  66.     printf(
  67.     "\t-do [s]\tPerform alternate function [s], where [s] is one of\n");
  68.     printf(
  69.     "\t\tESPRESSO, check, compact, contain, echo, essen, expand,\n");
  70.     printf(
  71.     "\t\tintersect, irred, lexsort, map, mincov, mv_reduce, pop,\n");
  72.     printf(
  73.     "\t\tprimes, qm, reduce, sharp, stats, taut, union, unravel, verify\n");
  74.     exit(0);
  75. }
  76.  
  77. main(argc, argv)
  78. int argc;
  79. char *argv[];
  80. {
  81.     pPLA PLA, PLA1;
  82.     int in_type, out_type = F_type, i, j, first_output, last_output;
  83.     bool readone, readtwo, verify_error = FALSE, print_solution;
  84.     char what_to_do[256];
  85.     cost_t cost, best_cost;
  86.     double start = ptime();
  87.  
  88.     init_runtime();
  89.  
  90.     /* Check for the help option */
  91.     if (check_arg(&argc, argv, "-help") || check_arg(&argc, argv, "?"))
  92.         usage();
  93.  
  94.     /* Scan the argument list for something to do (default is ESPRESSO) */
  95.     strcpy(what_to_do, "ESPRESSO");
  96.     for(i = 1; i < argc-1; i++)
  97.         if (equal(argv[i], "-do")) {
  98.             strcpy(what_to_do, argv[i+1]);
  99.             delete_arg(&argc, argv, i+1);
  100.             delete_arg(&argc, argv, i);
  101.             break;
  102.         }
  103.  
  104.     /* Scan the argument list for the output format */
  105.     if (option("echo"))
  106.         out_type = FDR_type;
  107.     for(i = 1; i < argc-1; i++)
  108.         if (equal(argv[i], "-out")) {
  109.             for(j = 0; pla_types[j].key != 0; j++)
  110.                 if (equal(pla_types[j].key+1, argv[i+1])) {
  111.                     out_type = pla_types[j].value;
  112.                     delete_arg(&argc, argv, i+1);
  113.                     delete_arg(&argc, argv, i);
  114.                     break;
  115.                 }
  116.             if (pla_types[j].key == 0) {
  117.                 fprintf(stderr, "espresso: Unknown output format %s\n",
  118.                     argv[i+1]);
  119.                 exit(-1);
  120.             } 
  121.             break;
  122.         }
  123.  
  124.     /* Check for other miscellaneous options */
  125.     chk_debug(&argc, argv);
  126.  
  127.     /* Espresso minimization options */
  128.     single_expand       = check_arg(&argc, argv, "-fast");
  129.     remove_essential    = ! check_arg(&argc, argv, "-ness");
  130.     force_irredundant   = ! check_arg(&argc, argv, "-nirr");
  131.     pos                 = check_arg(&argc, argv, "-pos");
  132.     kiss                = check_arg(&argc, argv, "-kiss");
  133.  
  134.     /* Miscellaneous options */
  135.     print_solution      = ! check_arg(&argc, argv, "-x");
  136.     summary = check_arg(&argc, argv, "-s") || option("stats");
  137.     trace = check_arg(&argc, argv, "-t") || (debug != 0);
  138.     mincov_exact = check_arg(&argc, argv, "-exact");
  139.  
  140.     /* Decide how many PLAs to read from files */
  141.     readone = ! (option("mincov") || option("mincov1"));
  142.     readtwo = option("union") || option("intersect") || option("sharp") ||
  143.         option("verify");
  144.     /* Decide if function needs offset and set in_type accordingly */
  145.     if (option("ESPRESSO") || option("expand") || option("echo") || 
  146.         option("mv_reduce") || option("primes") || option("qm") || 
  147.         option("newexpand") || option("opo") || option("badopo") ||
  148.         option("check"))
  149.         in_type = FD_type;
  150.     else
  151.         in_type = FDR_type;
  152.     if (summary || trace)
  153.         printf("# %s\n", VERSION);
  154.  
  155.     /* Read the (first) or only PLA */
  156.     if (readone || readtwo)
  157.         PLA = read_pla(&argc, argv, in_type);
  158.  
  159.     /* Read the second PLA if one is needed */
  160.     if (readtwo)
  161.         PLA1 = read_pla(&argc, argv, in_type);
  162.  
  163.     if (option("allphase")) {
  164.         first_output = atol(argv[1]);
  165.         last_output = atol(argv[2]);
  166.         argc -= 2;
  167.     }
  168.     chk_arglist(&argc, argv);
  169.  
  170.  
  171. /*
  172.     Now a giant IF-statement to decide what to do
  173. */
  174.  
  175.     /* Espresso minimization */
  176.     if (option("ESPRESSO")) {
  177.         pcover Fold = sf_save(PLA->F);
  178.         PLA->F = espresso(PLA->F, PLA->D, PLA->R);
  179.         EXECUTE(verify_error=verify(PLA->F,Fold,PLA->D), VERIFY_TIME, PLA->F);
  180.         if (verify_error) {
  181.             PLA->F = Fold;
  182.             print_solution = FALSE;
  183.             (void) check_consistency(PLA);
  184.         }
  185.  
  186.     /* Test drivers for each step of the ESPRESSO algorithm */
  187.     } else if (option("essen")) {
  188.         EXECUTE(PLA->F = essential(&(PLA->F), &(PLA->D)), ESSEN_TIME, PLA->F);
  189.     } else if (option("expand")) {
  190.         pcover Fold = sf_save(PLA->F);
  191.         EXECUTE(PLA->F=expand(PLA->F,PLA->R,FALSE,FALSE),EXPAND_TIME, PLA->F);
  192.         EXECUTE(verify_error=verify(PLA->F,Fold,PLA->D), VERIFY_TIME, PLA->F);
  193.     } else if (option("irred")) {
  194.         pcover Fold = sf_save(PLA->F);
  195.         EXECUTE(PLA->F = irredundant(PLA->F, PLA->D), IRRED_TIME, PLA->F);
  196.         EXECUTE(verify_error=verify(PLA->F,Fold,PLA->D), VERIFY_TIME, PLA->F);
  197.     } else if (option("reduce")) {
  198.         pcover Fold = sf_save(PLA->F);
  199.         EXECUTE(PLA->F = reduce(PLA->F, PLA->D), REDUCE_TIME, PLA->F);
  200.         EXECUTE(verify_error=verify(PLA->F,Fold,PLA->D), VERIFY_TIME, PLA->F);
  201.     } else if (option("taut")) {
  202.         printf("ON-set is%sa tautology\n",
  203.             tautology(cube1list(PLA->F)) ? " " : " not ");
  204.         print_solution = FALSE;
  205.     } else if (option("verify")) {
  206.         pcover Fold = PLA->F, F = PLA1->F, Dold = PLA->D;
  207.         EXECUTE(verify_error=verify(F, Fold, Dold), VERIFY_TIME, PLA->F);
  208.     } else if (option("mv_reduce")) {
  209.         pcover F = PLA->F, D = PLA->D, R = PLA->R;
  210.         cover_cost(PLA->F, &best_cost);
  211.         do {
  212.             EXECUTE_BREAK( F = mv_reduce(F, D), MV_REDUCE_TIME, F);
  213.             copy_cost(&cost, &best_cost);
  214.             EXECUTE_BREAK( F = expand(F, R, FALSE, TRUE), RAISE_IN_TIME, F);
  215.             copy_cost(&cost, &best_cost);
  216.         } while (force_irredundant);
  217.         PLA->F = F;
  218.     } else if (option("mincov") || option("mincov1")) {
  219.         int best;
  220.         pset_family A = read_set_family(stdin);
  221.         pset c;
  222.         if (option("mincov"))
  223.             c = minimum_cover(A, &best);
  224. /*      else
  225.             c = exact_minimum_cover(A);*/
  226.         printf("minimum cover has %d elements\n", set_ord(c));
  227.         sf_free(A);
  228.         set_free(c);
  229.         print_solution = FALSE;
  230.     }
  231.  
  232.     /* The presto/pop algorithm using unate tautology */
  233.     else if (option("pop")) {
  234.         pcover Fold = sf_save(PLA->F); bool better;
  235.         EXECUTE(better = pop_expand(&(PLA->F), PLA->D), EXPAND_TIME, PLA->F);
  236.         do {
  237.             EXECUTE(better=pop_reduce(&(PLA->F),PLA->D), REDUCE_TIME, PLA->F);
  238.             if (! better)
  239.                 break;
  240.             EXECUTE(better=pop_expand(&(PLA->F),PLA->D), EXPAND_TIME, PLA->F);
  241.         } while (better);
  242.         EXECUTE(verify_error=verify(PLA->F,Fold,PLA->D), VERIFY_TIME, PLA->F);
  243.     }
  244.  
  245.     /* A more traditional type of minimization */
  246.     else if (option("primes") || option("qm")) {
  247.         free_cover(PLA->F);
  248.         PLA->R = sf_contain(unravel(PLA->R, cube.num_vars-1));
  249.         EXEC(PLA->R = lex_sort(PLA->R), "SORT       ", PLA->R);
  250.         EXEC(PLA->F = cb_sharp(cube.fullset, PLA->R), "PRIMES     ", PLA->F);
  251.         if (option("qm"))
  252.             EXEC(PLA->F = irredundant(PLA->F, PLA->D), "COVER      ", PLA->F);
  253.     }
  254.  
  255.     else if (option("dcset")) { /* find where we intersect DC set */
  256.         pcover T;
  257.         EXEC(T = cv_intersect(PLA->F, PLA->D), "INTERSECT  ", T);
  258.         PLA->R = complement(cube1list(T));
  259.         EXEC(PLA->F=espresso(T,new_cover(0),PLA->R), "ESPRESSO   ", PLA->F);
  260.     }
  261.  
  262.     else if (option("map"))
  263.         map(PLA->F);
  264.     else if (option("opo"))
  265.         phase_assignment(PLA);
  266.     else if (option("badopo")) {
  267. /*      PLA->phase = badopo(PLA->F);
  268.         set_phase(PLA);*/
  269.         minall(PLA);
  270.     } else if (option("allphase"))
  271.         allphase(PLA, first_output, last_output);
  272.  
  273.  
  274.     /* Simple things ... */
  275.     else if (option("echo"))                    /* merely echo the pla */
  276.         ;
  277.     else if (option("contain"))                 /* single cube containment */
  278.         PLA->F = sf_contain(PLA->F);
  279.     else if (option("intersect"))               /* cover intersection */
  280.         PLA->F = cv_intersect(PLA->F, PLA1->F);
  281.     else if (option("union"))                   /* cover union */
  282.         PLA->F = sf_union(PLA->F, PLA1->F);
  283.     else if (option("sharp"))                   /* cover sharp */
  284.         PLA->F = cv_sharp(PLA->F, PLA1->F);
  285.     else if (option("lexsort"))                 /* lexical sort order */
  286.         PLA->F = lex_sort(PLA->F);              
  287.     else if (option("miniexpord"))              /* mini expand order */
  288.         PLA->F = mini_order(PLA->F, ascend);
  289.     else if (option("miniredord"))              /* mini reduce order */
  290.         PLA->F = mini_order(PLA->F, descend);
  291.     else if (option("stats"))                   /* print info on size */
  292.         summary = print_solution = FALSE;
  293.     else if (option("unravel"))                 /* unravel output */
  294.         PLA->F = unravel(PLA->F, cube.num_vars - 1);
  295.     else if (option("minterms"))                /* explode into minterms ! */
  296.         PLA->F = sf_contain(unravel(PLA->F, 0));
  297.     else if (option("d1merge"))                 /* full distance-1 merge */
  298.         for(i = 0; i < cube.num_vars; i++)
  299.             PLA->F = d1merge(PLA->F, i);
  300.     else if (option("compact"))                 /* distance-1 merge outputs */
  301.         PLA->F = d1merge(PLA->F, cube.num_vars - 1);
  302.     else if (option("check")) {                 /* check consistency */
  303.         verify_error = check_consistency(PLA);
  304.         print_solution = FALSE;
  305.  
  306.     /* Anything else is an error */
  307.     } else {
  308.         fprintf(stderr, "Unknown program option %s\n", what_to_do);
  309.         exit(-1);
  310.     }
  311.  
  312.     if (trace)
  313.         runtime();
  314.     if (summary || trace) {
  315.         mem_stats();
  316.         if (! option("mincov") || option("mincov1"))
  317.             print_trace(PLA->F, what_to_do, ptime() - start);
  318.     }
  319.     if (print_solution)
  320.         fprint_pla(stdout, PLA, out_type);
  321.  
  322.     if (verify_error)
  323.         fatal("Minimized cover verification failed");
  324.     exit(0);
  325. }
  326.